import java.util.Iterator;
public class RandomQueue<Item> implements Iterable<Item>
{
	int entries;
	Item[] queue;
	StdRandom random;
	
	public RandomQueue(){ // create an empty random queue
		entries = 0;
		queue = (Item[]) new Object[1];
	}
	
	public boolean isEmpty(){ // is it empty?
		return size() == 0;
	}
	
	public int size(){ // return the number of elements
		return entries;
	}
	
	public void enqueue(Item item){ // add an item
		if (entries == queue.length) resize(2 * queue.length);
		queue[entries] = item;
		entries++;
	}
	
	public Item sample(){ // return (but do not remove) a random item
		return queue[random.uniform(entries)];
	}
	
	public Item dequeue(){ // remove and return a random item
		int r = random.uniform(entries);
		Item tempItem = queue[r];
		queue[r] = queue[entries-1];
		queue[entries-1] = null;
		entries--;
		if (entries > 0 && entries == queue.length/4) resize(queue.length/2);
		return tempItem;
	}
	
	private void resize(int capacity)
	{
	   Item[] copy = (Item[]) new Object[capacity];
	   for (int i = 0; i < size(); i++)
	      copy[i] = queue[i];
	   queue = copy;
	}
	
	public Iterator<Item> iterator(){ // return an iterator over the items in random order
		return new RandomArrayIterator();
	}
	
	private class RandomArrayIterator implements Iterator<Item>
	{
		private int i = entries;
		private Item[] items = queue.clone();

		public boolean hasNext() { return i > 0; }
		public Item next() {
			int r = random.uniform(i);
			Item temp = items[r];
			
			items[r] = items[i-1];
			items[i-1] = null;
			i--;
			return temp;
		}
		public void remove(){};
	}

	public static void main(String args[])
	{
		// Build a queue containing the Integers 1,2,...,6:
		RandomQueue<Integer> Q= new RandomQueue<Integer>();
	    for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!

	    // Print 30 dice rolls to standard output
	    StdOut.print("Some dice rolls: ");
	    for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
	    StdOut.println();

	    // Let's be more serious: do they really behave like dice rolls?
	    int[] rolls= new int [10000];
	    for (int i = 0; i < 10000; ++i)
	      rolls[i] = Q.sample(); // autounboxing! Also cool!
	    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
	    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
			  StdStats.stddev(rolls));

	    // Let's look at the iterator. First, we make a queue of colours:

	    RandomQueue<String> C= new RandomQueue<String>();
	    C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

	    Iterator I= C.iterator();
	    Iterator J= C.iterator();

	    StdOut.print("Two colours from first shuffle: ");
	    StdOut.print(I.next()+" ");
	    StdOut.print(I.next()+" ");

	    StdOut.print("\nEntire second shuffle: ");
	    while (J.hasNext()) StdOut.print(J.next()+" ");

	    StdOut.print("\nRemaining two colours from first shuffle: ");
	    StdOut.print(I.next()+" ");
	    StdOut.println(I.next());
	}
}